export default class MaxHeap<T> {
  data: T[] = [];
  private length: number = 0;

  constructor(arr: T[] = []) {
    if (arr.length === 0) return;
    this.buildHeap(arr);
  }

  private swap(i: number, j: number) {
    const temp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j] = temp;
  }

  insert(value: T) {
    this.data.push(value);
    this.length++;

    // 维护堆的特性
    this.heapify_up();
  }

  private heapify_up() {
    let index = this.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor(index / 2 - 1);
      if (this.data[index] <= this.data[parentIndex]) {
        break;
      }

      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  extract(): T | undefined {
    if (this.length === 0) return undefined;
    if (this.length === 1) {
      this.length--;
      return this.data.shift();
    }

    const topValue = this.data[0]; // 不能直接使用shift操作，使用shift操作会打乱堆结构的特性
    this.data[0] = this.data.pop()!; // 将数组中的最后一个元素删除, 并替换到堆首元素
    this.length--;

    // 维护最大堆特性：下滤操作
    this.heapify_down(0);
    return topValue;
  }

  private heapify_down(start: number) {
    let index = start;
    while (2 * index + 1 <= this.length - 1) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let largetIndex = leftChildIndex;
      if (rightChildIndex < this.length && this.data[rightChildIndex] > this.data[leftChildIndex]) {
        largetIndex = rightChildIndex;
      }

      if (this.data[index] >= this.data[largetIndex]) {
        break;
      }

      this.swap(index, largetIndex);
      index = largetIndex;
    }
  }

  peek(): T | undefined {
    return this.data[0];
  }

  size() {
    return this.length;
  }

  isEmpty() {
    return this.length === 0;
  }

  buildHeap(arr: T[]) {
    this.data = arr;
    this.length = arr.length;

    // 从第一个非叶子节点，开始进行下滤操作
    const start = Math.floor((this.length - 1) / 2);
    for (let i = start; i >= 0; i--) {
      this.heapify_down(i);
    }
  }
}

const arr = [19, 100, 36, 17, 3, 25, 1, 2, 7];
const heap = new MaxHeap(arr);
console.log(heap.data);
